1. Field of the Invention
This invention relates to public-key cryptographic systems and in particular to public-key digital signature techniques. The techniques and apparatus are useful for securing computer readable information, such as executable instructions and data. They are also useful for identifying authorized copies of devices containing computer readable information.
The typical purpose of the cryptographic technique is to so disguise a message that it would be difficult if not impossible in practice to encode or decode the message without knowledge of a key. Public-key crypotsystems permit parties to communicate securely with privacy but without prior exchange of keys, and in typical applications such as electronic funds transfer, allowing the creation of digital codes which serve the same function as a handwritten signature for document authentication.
2. Description of the Prior Art
The current model for non-public-key data encryption is the IBM-designed standard adopted by the National Bureau of Standards and generally designated the Data Encryption Standard (DES) cipher.
The need for communicating a secure encryption key over an insecure channel was solved by the invention of public-key concept by the present inventor in conjunction with others at Stanford University. Public-key systems are based on the use of two separate but mathematically related keys, one key for enciphering and the other key for deciphering. The functions chosen for relating the enciphering key to the deciphering key are such that computing the deciphering key from the enciphering key is computationally infeasible. Such functions are popularly referred to as trap-door functions, because they are computationally feasible in only one direction. Reference may be had to Diffie and Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory, November 1976, pages 664-654, and Diffie and Hellman, "Privacy and Authentication: an Introduction to Cryptography," Proc. IEEE, Vol. 67, March 1979, pp. 397-427.
There are a number of implementations of the general concept. For example, U.S. Pat. No. 4,218,582 describes a so-called trap-door knapsack to implement the public-key cryptosystem in message communications.
A somewhat different function which is relatively easy to implement is described by Rivest, Shamir and Adleman, "A Method for Obtaining Digital Signatures and Public-Key Crypto Systems" Communications of the ACM, February, 1978 pages 120-126. The Rivest et al. (RSA) method suggests the use of two large secret prime numbers whose product is a publicly specified number. According to the RSA method, the message is encrypted by representing it as a number M, raising M to a publicly specified power e, then taking the remainder when the result is divided by the publicly specified product n of the two large secret prime numbers, designated p and q. The result is an encrypted message C. The message is decrypted by raising the encrypted message C to a secret power designated d and then by taking the remainder when the result is divided by the publicly specified product n. The publicly specified power e is chosen to be related to the secret power d according to the following relationship: EQU e*d=1 (mod(p-1)*(q-1)).
The difficulty in breaking the code rests in part in the difficulty in factoring the publicly specified product n.
Encryption techniques employing this method are referred to as RSA public-key cryptotechniques.
The RSA cryptosystem prohibits a special case of the publicly specified power e, namely e=2. The RSA cryptosystem requires that e be relatively prime to, i.e., have no factor in common with, the values p-1 and q-1 where p and q are the two large secret prime numbers. Since both p and q are odd numbers because they are prime numbers, p-1 and q-1 are both divisible by 2 and thus e=2 is not allowed according to the RSA cryptosystem.
According to the RSA cryptosystem, additional protection against sophisticated factoring algorithms for p and q may be provided where p and q differ in length by a few digits and p-1 contains a large prime factor s, and also where q-1 contains a large prime factor u, s-1 contains a large prime factor s', u-1 contains a large prime factor u', and the greatest common denominator of p-1 and q-1 is small.
A system somewhat related to the RSA system has been proposed by Michael Rabin, the "Digitalized Signatures and Public-Key Functions as Intractable as Factorization," MIT Laboratory for Computer Science Technical Report 212, January 1979. Rabin suggested a different encrypting and decrypting function somewhat related to the RSA method. The Rabin system, however, works with functions which violate the RSA criteria. Reference is made to the work of RSA and Rabin for further information.